## 单向链表
## godot中只有数组, 数组这种数据结构查询较快
## 但插入删除移动数据效率较慢
## 这是一个自制的链表数据结构, 弥补godot引擎无链表的不足
class_name LinkedList

var head: ListNode = null  # 链表头节点
var size := 0  # 链表长度

## 在链表末尾添加元素
func append(value: Object) -> void:
	var new_node = ListNode.new(value)
	if head == null:
		head = new_node
	else:
		var current = head
		while current.next != null:
			current = current.next
		current.next = new_node
	size += 1

## 在指定索引插入元素
func insert(value: Object, index: int) -> void:
	if index < 0 or index > size:
		push_error("索引越界")
		return
	var new_node = ListNode.new(value)
	if index == 0:
		new_node.next = head
		head = new_node
	else:
		var current = head
		for i in range(index - 1):
			current = current.next
		new_node.next = current.next
		current.next = new_node
	size += 1

## 删除指定值的节点（只删除第一个匹配项）
func delete(value: Object) -> bool:
	if head == null:
		return false
	if head.value == value:
		head = head.next
		size -= 1
		return true
	var current = head
	while current.next != null:
		if current.next.value == value:
			current.next = current.next.next
			size -= 1
			return true
		current = current.next
	return false

## 遍历链表并打印所有值
func print_list() -> void:
	var current = head
	while current != null:
		print(current.value)
		current = current.next

## 获得索引处的元素
func getItem(index: int) -> Object:
	if index < 0 or index >= size:
		push_error("索引越界: %d (链表长度: %d)" % [index, size])
		return null
	var current = head
	for i in range(index):
		current = current.next
	return current.value
